package leetCode.q236;

public class Di_gui {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 定义出口
        if (root == null || root == p || q == root) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {//左子树找到了并且右子树也找到了
            return root;
        } else if (left != null) {//只有左子树找到了
            return left;
        } else {//右子树找到了或者全没找到
            return right;
        }
    }
}
